Control de la concurrencia (página 2)

Partes: 1, 2

9
La actualización temporal (o lectura sucia)
T1 actualiza un elemento X de la BD y luego falla, pero antes de que se restaure el valor original de X, T2 tiene acceso al «valor temporal» de X
… y problemas de la concurrencia
Problemas potenciales provocados por la concurrencia
T1
leer_elemento(X);
X:= X-N;
escribir_elemento(X);

leer_elemento(Y);
…
T2

leer_elemento(X);
X:= X+M;
escribir_elemento(X);
T1 falla y debe devolver a X su antiguo valor; pero mientras, T2 ha leído el valor ‘temporal’ incorrecto de X (dato sucio)

10
El resumen incorrecto
Otra transacción T3 calcula una función agregada de resumen sobre varios registros (suma las plazas reservadas para todos los vuelos), mientras otras transacciones, como T1, actualizan dichos registros: puede que T3 considere unos registros antes de ser actualizados y otros después
… y problemas de la concurrencia
Problemas potenciales provocados por la concurrencia
T1

leer_elemento(X);
X:= X-N;
escribir_elemento(X);

leer_elemento(Y);
Y:=Y+N;
escribir_elemento(Y);
T3
suma:=0;
leer_elemento(A);
suma:= suma+A;
…
…
…

leer_elemento(X);
suma:= suma+X;
leer_elemento(Y);
suma:= suma+Y;
…
…
…
T3 lee X después de restar N, pero lee Y antes de sumar N, así que el resultado es un resumen incorrecto (discrepancia de N)

11
La lectura no repetible
T4 lee un elemento X dos veces y otra transacción, como T1, modifica dicho X entre las dos lecturas: T4 recibe diferentes valores para el mismo elemento
… y problemas de la concurrencia
Problemas potenciales provocados por la concurrencia
T1
leer_elemento(X);
X:= X-N;

escribir_elemento(X);
leer_elemento(Y);

Y:=Y+N;
escribir_elemento(Y);
T4

leer_elemento(X);

…
leer_elemento(X);
…
T4 lee X antes de restar N
T4 lee X después de restar N

12
Objetivo de un protocolo de control de concurrencia:
Planificar las transacciones de forma que no ocurran interferencias entre ellas, y así evitar la aparición de los problemas mencionados
Solución obvia: no permitir intercalación de operaciones de varias transacciones
Serializabilidad
Motivación
(Gp:) Planificación A
(Gp:) T1
leer_elemento(X);
X:= X-N;
escribir_elemento(X);
leer_elemento(Y);
Y:=Y+N;
escribir_elemento(Y);
(Gp:) T2

leer_elemento(X);
X:= X+M;
escribir_elemento(X);

(Gp:) Planificación B
(Gp:) T1

leer_elemento(X);
X:= X-N;
escribir_elemento(X);
leer_elemento(Y);
Y:=Y+N;
escribir_elemento(Y);
(Gp:) T2
leer_elemento(X);
X:= X+M;
escribir_elemento(X);

13
Pero el objetivo de un SGBD multiusuario también es maximizar el grado de concurrencia del sistema
Si se permite la intercalación de operaciones, existen muchos órdenes posibles de ejecución de las transacciones
Serializabilidad
Motivación
¿Existe algún modo de identificar las ejecuciones que está garantizado que protegen la consistencia de la base de datos?
?Teoría de la Serializabilidad
(Gp:) Planificación C: actualización perdida!
(Gp:) T1
leer_elemento(X);
X:= X-N;

escribir_elemento(X);
leer_elemento(Y);

Y:=Y+N;
escribir_elemento(Y);
(Gp:) T2

leer_elemento(X);
X:= X+M;

escribir_elemento(X);

(Gp:) Planificación D: correcta!
(Gp:) T1
leer_elemento(X);
X:= X-N;
escribir_elemento(X);

leer_elemento(Y);
Y:=Y+N;
escribir_elemento(Y);
(Gp:) T2

leer_elemento(X);
X:= X+M;
escribir_elemento(X);

14
Cada transacción comprende una secuencia de operaciones que incluyen acciones de lectura y escritura en la BD, que finaliza con una confirmación (commit) o anulación (rollback)

Una planificación P de n transacciones concurrentes T1, T2 … Tn es una secuencia de las operaciones realizadas por dichas transacciones, sujeta a la restricción de que para cada transacción Ti que participa en P, sus operaciones aparecen en P en el mismo orden en el que ocurren en Ti
Serializabilidad
Planificación de transacciones

15
Para el control de la concurrencia (y recuperación de fallos) interesa prestar mayor atención a estas operaciones:

Ejemplos de planificaciones de transacciones
El subíndice de cada operación indica la transacción que la realiza
PA: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ; l2(X) ; e2(X) ; c2 ;
PB: l2(X) ; e2(X) ; c2 ; l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ;
PC: l1(X) ; l2(X) ; e1(X) ; l1(Y) ; e2(X) ; c2 ; e1(Y) ; c1 ;
PD: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;
PE: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; r1 ;
Serializabilidad
Planificación de transacciones

16
Una planificación serie P es aquella en la que las operaciones de cada transacción se ejecutan consecutivamente sin que se intercalen operaciones de otras transacciones
PA: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ; l2(X) ; e2(X) ; c2 ;
PB: l2(X) ; e2(X) ; c2 ; l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ;
Toda planificación serie es correcta ?BD consistente
Pero no se garantiza que los resultados de todas las ejecuciones en serie de las mismas transacciones sean idénticos
Ejemplo: cálculo del interés de una cuenta bancaria antes o después de realizar un ingreso considerable

en general, son inaceptables en la práctica (ineficiencia)
Serializabilidad
Planificación serie

17
Una planificación no serie P es aquella en la que las operaciones de un conjunto de transacciones concurrentes se ejecutan intercaladas
PC: l1(X) ; l2(X) ; e1(X) ; l1(Y) ; e2(X) ; c2 ; e1(Y) ; c1 ;
PD: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;

Hemos de determinar qué planificaciones no serie permiten llevar la BD a un estado al que pueda llegarse mediante una ejecución en serie
Serializabilidad
Planificación no serie
Este es el objetivo de la Serializabilidad
KO

18
Una planificación P (no serie) es serializable si es equivalente a alguna planificación serie de las mismas n transacciones
Una planificación que no es equivalente a ninguna ejecución en serie, es una planificación no serializable
Toda planificación serializable es correcta
Produce los mismos resultados que alguna ejecución en serie
Dos maneras de definir la equivalencia entre planificaciones:
Equivalencia por conflictos
Equivalencia de vistas
Serializabilidad
Planificación serializable

19
Si dos transacciones únicamente leen un determinado elemento de datos, no entran en conflicto entre sí y el orden de las operaciones no es importante
Si hay dos transacciones que leen o escriben elementos de datos independientes, no entran en conflicto entre sí y el orden de las operaciones no es importante
Si una de las transacciones escribe un elemento de datos y la otra lee o escribe el mismo elemento, entran en conflicto y el orden de las operaciones sí es importante
Serializabilidad
Equivalencia por conflictos

20
En una planificación, 2 operaciones están en conflicto si
pertenecen a diferentes transacciones,
tienen acceso al mismo elemento X,
y al menos una de ellas es escribir_elemento(X)

Operaciones en conflicto en las planificaciones PC y PD:

PC: l1(X) ; l2(X) ; e1(X) ; l1(Y) ; e2(X) ; c2 ; e1(Y) ; c1;

PD: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;

Dos planes son equivalentes por conflictos si el orden de cualesquiera dos operaciones en conflicto es el mismo en ambos planes
Serializabilidad
Equivalencia por conflictos

21
Una planificación P es serializable por conflictos si equivale por conflictos a alguna planificación serie S
Podremos intercambiar cada dos operaciones de P consecutivas de transacciones distintas y sin conflicto, hasta obtener la planificación serie equivalente
PD : l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;
PD1: l1(X) ; e1(X) ; l2(X) ; e2(X) ; l1(Y) ; c2 ; e1(Y) ; c1 ;
PD2: l1(X) ; e1(X) ; l2(X) ; e2(X) ; l1(Y) ; e1(Y) ; c2 ; c1 ;
PD3: l1(X) ; e1(X) ; l2(X) ; e2(X) ; l1(Y) ; e1(Y) ; c1 ; c2 ;
PD4: l1(X) ; e1(X) ; l2(X) ; l1(Y) ; e2(X) ; e1(Y) ; c1 ; c2 ;
PD5: l1(X) ; e1(X) ; l2(X) ; l1(Y) ; e1(Y) ; e2(X) ; c1 ; c2 ;
PD6: l1(X) ; e1(X) ; l2(X) ; l1(Y) ; e1(Y) ; c1 ; e2(X) ; c2 ;
PD7: l1(X) ; e1(X) ; l1(Y) ; l2(X) ; e1(Y) ; c1 ; e2(X) ; c2 ;
PD8: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; l2(X) ; c1 ; e2(X) ; c2 ;
PD9: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ; l2(X) ; e2(X) ; c2 ;
Serializabilidad
Planificación serializable por conflictos
¡Es una planificación serie!
PD es serializable

22
Construcción del grafo de precedencia (o de serialización)
Es un grafo dirigido G = ( N, A )
N es un conjunto de nodos y A es un conjunto de aristas dirigidas
Algoritmo:
Crear un nodo por cada transacción Ti en P
Crear una arista Tj ?Tk si Tk lee el valor de un elemento después de que Tj lo haya escrito
Crear una arista Tj ?Tk si Tk escribe el valor de un elemento después de que Tj lo haya leído
Crear una arista Tj ?Tk si Tk escribe el valor de un elemento después de que Tj lo haya escrito

Ti
Serializabilidad
Detección de la serializabilidad por conflictos
(Gp:) Tj
(Gp:) Tk

23
Una arista Tj ? Tk indica que Tj debe aparecer antes que Tk en una planificación serie equivalente a P, pues dos operaciones en conflicto aparecen en dicho orden en P
Si el grafo contiene un ciclo, P no es serializable por conflictos
Un ciclo es una secuencia de aristas C=((Tj ?Tk), (Tk ?Tp),… (Ti ?Tj))
Si no hay ciclos en el grafo, P es serializable
Es posible obtener una planificación serie S equivalente a P, mediante una ordenación topológica de los nodos
Serializabilidad
Detección de la serializabilidad por conflictos (y 2)
(Gp:) T1
(Gp:) T2
(Gp:) PA

(Gp:) T1
(Gp:) T2
(Gp:) PB

(Gp:) T1
(Gp:) T2
(Gp:) PC

(Gp:) T1
(Gp:) T2
(Gp:) PD

24
Planificación E
Serializabilidad
Ejemplo de planificación no serializable
Transacción T1
leer_elemento(X);
escribir_elemento(X);
leer_elemento(Y);
escribir_elemento(Y);
Transacción T2
leer_elemento(Z);
leer_elemento(Y);
escribir_elemento(Y);
leer_elemento(X);
escribir_elemento(X);
Transacción T3
leer_elemento(Y);
leer_elemento(Z);
escribir_elemento(Y);
escribir_elemento(Z);
T1

leer_elemento(X);
escribir_elemento(X);

leer_elemento(Y);
escribir_elemento(Y);
T2
leer_elemento(Z);
leer_elemento(Y);
escribir_elemento(Y);

leer_elemento(X);

escribir_elemento(X);
T3

leer_elemento(Y);
leer_elemento(Z);

escribir_elemento(Y);
escribir_elemento(Z);
(Gp:) T1
(Gp:) T2
(Gp:) Y
(Gp:) X
(Gp:) T3
(Gp:) Y,Z
(Gp:) Y

Hay dos ciclos:
T1?T2?T1 y
T1?T2?T3?T1

25
Planificación F
Serializabilidad
Ejemplo de planificación serializable
Transacción T1
leer_elemento(X);
escribir_elemento(X);
leer_elemento(Y);
escribir_elemento(Y);
Transacción T2
leer_elemento(Z);
leer_elemento(Y);
escribir_elemento(Y);
leer_elemento(X);
escribir_elemento(X);
Transacción T3
leer_elemento(Y);
leer_elemento(Z);
escribir_elemento(Y);
escribir_elemento(Z);
T1

leer_elemento(X);
escribir_elemento(X);

leer_elemento(Y);
escribir_elemento(Y);
T2

leer_elemento(Z);

leer_elemento(Y);
escribir_elemento(Y);
leer_elemento(X);
escribir_elemento(X);
T3
leer_elemento(Y);
leer_elemento(Z);

escribir_elemento(Y);
escribir_elemento(Z);
(Gp:) T1
(Gp:) T2
(Gp:) X,Y
(Gp:) T3
(Gp:) Y,Z
(Gp:) Y

La planificación serie equivalente es T3 ? T1 ? T2

26
(Gp:) Es el SO el que distribuye los recursos
para los procesos, y determina la
intercalación de las operaciones de las transacciones concurrentes
(ejecutadas como procesos del SO)
(Gp:) Planificación P (ordenamiento de las operaciones)
(Gp:) Carga del sistema
Momento de introducción de las transacciones
Prioridades de los procesos
…
(Gp:) Planificador deTareas del SO

Serializabilidad
Aplicaciones de la serializabilidad
Es necesario encontrar técnicas que garanticen la serializabilidad, sin tener que verificar a posteriori
¡¡enfoque muy poco práctico!!
(Gp:) Parece, pues, que habría que comprobar si P es serializable una vez ejecutadas las transacciones incluidas en P…
(Gp:) Ejecución de Transacciones
(Gp:) NO
(Gp:) SI
(Gp:) OK
(Gp:) Cancelar el efecto de P
(Gp:) reintentar
(Gp:) ¿P serializable?

27
Métodos basados en la teoría de la serializabilidad, que definen un conjunto de reglas (o protocolo) tal que…
si todas las transacciones las cumplen, o
el subsistema de control de concurrencia del SGBD las impone (automáticamente)
… se asegura la serializabilidad de toda planificación de transacciones

Clasificación
Métodos de bloqueo
Métodos de marca de tiempo
Técnicas de multiversión
Métodos optimistas
Técnicas de control de concurrencia

28
Uso de bloqueos para controlar el acceso concurrente a los elementos de datos almacenados en la base de datos
Reglas básicas del bloqueo:
Bloqueo compartido: si una transacción tiene un bloqueo compartido sobre un elemento de datos, puede leer el elemento, pero no actualizarlo (escribir)
Varias transacciones pueden mantener a la vez bloqueos compartidos sobre el mismo elemento
Bloqueo exclusivo: si una transacción tiene un bloqueo exclusivo sobre un elemento de datos, puede leer y actualizar (escribir) el elemento
Un bloqueo exclusivo proporciona acceso exclusivo al elemento
Técnicas de control de concurrencia
Métodos de bloqueo

29
Reglas de uso de los bloqueos
1. T debe emitir bloquear_lectura(X) o bloquear_escritura(X) antes de ejecutar una operación leer_elemento(X)
2. T debe emitir bloquear_escritura(X) antes de realizar una operación escribir_elemento(X) en T
3. T debe emitir desbloquear(X) una vez completadas todas las operaciones leer_elemento(X) y escribir_elemento(X)
4. Si T ya posee un bloqueo, compartido o exclusivo, sobre X no emitirá bloquear_lectura(X) ni bloquear_escritura(X)
*esta regla puede permitir excepciones: mejora y reducción de bloqueos*
5. T no emitirá desbloquear(X) salvo si posee un bloqueo, compartido o exclusivo, sobre X
Técnicas de control de concurrencia
Métodos de bloqueo

30
Cuando una transacción T solicita un bloqueo…
Si el elemento no ha sido ya bloqueado por otra transacción, se le concede el bloqueo
Si el elemento sí está bloqueado, el SGBD determina si la solicitud es compatible con el bloqueo existente:
Si se pide un bloqueo compartido sobre un elemento que ya tiene un bloqueo compartido, el bloqueo será concedido a T
En otro caso, T debe esperar hasta que se libere el bloqueo existente
Una transacción que obtiene un bloqueo lo mantiene hasta que lo libera explícitamente o termina (commit o rollback)
Sólo cuando se libera un bloqueo exclusivo los efectos de la escritura serán visibles para las demás transacciones
Técnicas de control de concurrencia
Métodos de bloqueo

31
Algunos sistemas permiten la mejora (o promoción) y la reducción (o degradación) de bloqueos
Aumenta el nivel de concurrencia del sistema
Si T emitió bloquear_lectura(X), más tarde puede mejorarlo a bloqueo exclusivo emitiendo bloquear_escritura(X)
Si T es la única que tiene un bloqueo compartido sobre X, se le concede la solicitud
En otro caso, T debe esperar
Si T emitió bloquear_escritura(X), más tarde puede reducirlo a un bloqueo compartido emitiendo bloquear_lectura(X)
Así permite que otras transacciones lean X
Técnicas de control de concurrencia
Métodos de bloqueo

32
El uso de bloqueos para la programación de transacciones no garantiza la serializabilidad de las planificaciones
Técnicas de control de concurrencia
Métodos de bloqueo
(Gp:) Planificación G
(Gp:) T4
bloquear_lectura(Y);
leer_elemento(Y);
desbloquear(Y);

bloquear_escritura(X);
leer_elemento(X);
X:=X+Y;
escribir_elemento(X);
desbloquear(X);
(Gp:) T5

bloquear_lectura(X);
leer_elemento(X);
desbloquear(X);
bloquear_escritura(Y); leer_elemento(Y);
Y:=X+Y;
escribir_elemento(Y);
desbloquear(Y);

Transacción T4
bloquear_lectura(Y);
leer_elemento(Y);
desbloquear(Y);
bloquear_escritura(X);
leer_elemento(X);
X:=X+Y;
escribir_elemento(X);
desbloquear(X);
Transacción T5
bloquear_lectura(X);
leer_elemento(X);
desbloquear(X);
bloquear_escritura(Y); leer_elemento(Y);
Y:=X+Y;
escribir_elemento(Y);
desbloquear(Y);
Valores iniciales: X=20, Y=30
Resultados de las planificaciones serie:
T4?T5: X=50, Y=80
T5?T4: X=70, Y=50
Resultado de la planificación G:
X=50, Y=50 (No serializable!)

33
Es necesario seguir un protocolo adicional que indique dónde colocar las operaciones de bloqueo y desbloqueo dentro de las transacciones
El más conocido es el Bloqueo en Dos Fases (B2F)
Una transacción T sigue el protocolo de bloqueo en dos fases si todas las operaciones de bloqueo preceden a la primera operación de desbloqueo
De este modo, podemos ver T dividida en dos fases:
Fase de expansión (o crecimiento)
T puede adquirir bloqueos
T no puede liberar ningún bloqueo
Fase de contracción
T puede liberar bloqueos existentes
T no puede adquirir ningún bloqueo
Técnicas de control de concurrencia
Métodos de bloqueo: Bloqueo en dos fases

34
Si el sistema permite mejorar y reducir bloqueos…
La mejora sólo puede tener lugar en la fase de expansión
La reducción sólo puede realizarse en la fase de contracción
En el código de T, un bloquear_lectura(X) puede aparecer en la fase de contracción de T sólo si reduce un bloqueo exclusivo a uno compartido
Técnicas de control de concurrencia
Bloqueo en dos fases
Transacción T4’
bloquear_lectura(Y);
leer_elemento(Y);
bloquear_escritura(X);
desbloquear(Y);
leer_elemento(X);
X:=X+Y;
escribir_elemento(X);
desbloquear(X);
Transacción T5’
bloquear_lectura(X);
leer_elemento(X);
bloquear_escritura(Y); desbloquear(X); leer_elemento(Y);
Y:=X+Y;
escribir_elemento(Y);
desbloquear(Y);

35
Si toda transacción de una planificación sigue el protocolo de bloqueo en dos fases, entonces la planificación es serializable
Ventaja
Ya no es necesario comprobar la serializabilidad de las planificaciones
Inconvenientes
El B2F puede limitar el grado de concurrencia en un plan
Emplear bloqueos puede provocar problemas de …
Interbloqueo (bloqueo mortal o abrazo mortal)
Bloqueo indefinido (o espera indefinida)
Técnicas de control de concurrencia
Bloqueo en dos fases

36
T debe bloquear todos los elementos a los que tendrá acceso (lectura o escritura) antes de comenzar a ejecutarse
Si no es posible bloquear algún elemento, T no bloqueará ninguno y esperará para reintentarlo más tarde
Protocolo libre de interbloqueo
Técnicas de control de concurrencia
Bloqueo en dos fases conservador o estático
Bloqueo en dos fases estricto el más utilizado
T no libera ningún bloqueo exclusivo hasta terminar (con COMMIT o ROLLBACK)
Ninguna transacción lee o escribe un elemento modificado por T, salvo si T se ha completado?planificación estricta
Puede sufrir interbloqueo (salvo si se combina con B2F conservador)
Bloqueo en dos fases riguroso más restrictivo que el B2F estricto
T no libera ningún bloqueo compartido ni exclusivo hasta terminar (con COMMIT o ROLLBACK) ?planificación estricta

37
Situación en la que cada una de dos (o más) transacciones está esperando a que se libere un bloqueo establecido por la otra transacción
Técnicas de control de concurrencia
El problema del interbloqueo
T6
bloquear_escritura(X);
leer_elemento(X);
X:=X-10;
escribir_elemento(X);
bloquear_escritura(Y);
[… en espera …]
T7

bloquear_escritura(Y);
leer_elemento(Y);
Y:=Y+100;
escribir_elemento(Y); bloquear_escritura(Y);
[… en espera …]
El SGBD ha de reconocer un interbloqueo y romperlo:
Abortar una o más transacciones
Se deshacen sus escrituras y se liberan sus bloqueos
Así, el resto de transacciones podrá continuar su ejecución
Reiniciar automáticamente las transacciones abortadas

38
Hay 3 técnicas generales para gestionar los interbloqueos
Temporizaciones de bloqueos
Prevención de interbloqueos
Detección de interbloqueos
Conviene detectar interbloqueos cuando se sabe que hay poca interferencia entre transacciones, es decir si…
Las transacciones son cortas y bloquean pocos elementos, o
La carga de transacciones es pequeña
En otro caso, conviene usar temporizaciones o técnicas de prevención

Es más difícil prevenir que utilizar temporizaciones o que detectarlos y romperlos, por lo que en la práctica los sistemas no suelen emplear las técnicas de prevención
Técnicas de control de concurrencia
El problema del interbloqueo

39
Una transacción que solicita un bloqueo sólo esperará durante un período de tiempo predefinido por el sistema
Si no se concede el bloqueo durante ese tiempo, se producirá un ‘fin de temporización’: el SGBD asumirá que la transacción está interbloqueada (aunque puede que no), la abortará y la reiniciará automáticamente
Es una solución muy sencilla y práctica
Pero puede hacer que sean abortadas y reiniciadas transacciones que en realidad no están en un interbloqueo

Técnicas de control de concurrencia
Temporizaciones de bloqueos

40
Ordenar las transacciones usando marcas temporales de transacción MT(T):
Identificador único para T
Las MT se ordenan según se inician las transacciones
La T más antigua tiene la MT(T) menor

?Sea Tj que intenta bloquear el elemento de datos X , pero X ya está bloqueado por Tk con un candado en conflicto
Algoritmo Esperar – Morir
si MT(Tj) < MT(Tk) entonces Tj puede esperar
si no, se aborta Tj (Tj muere) y
se reinicia después con la misma marca de tiempo
Una Tj más antigua espera a que termine otra Tk más reciente
Una Tj más reciente que solicita un elemento bloqueado por una Tk más antigua, es abortada (muere) y reiniciada
Técnicas de control de concurrencia
Prevención de interbloqueos

41
Algoritmo Herir – Esperar
si MT(Tj) < MT(Tk) entonces se aborta Tk (Tj hiere a Tk) y
se reinicia después con la misma MT
si no, Tj puede esperar
Una Tj más reciente espera a que termine una Tk más antigua
Una Tj más antigua que solicita un elemento bloqueado por una Tk más reciente, hace que la más reciente sea abortada (es herida) y reiniciada
Inconvenientes
Ambos algoritmos hacen que sean abortadas y reiniciadas transacciones que podrían provocar un bloqueo mortal, aunque tal cosa nunca ocurriera!
En el algoritmo Esperar-Morir, una Tj podría abortar y reiniciarse varias veces seguidas si Tk más antigua sigue bloqueando el X que Tj solicita
Técnicas de control de concurrencia
Prevención de interbloqueos

42
Verificación periódica del estado del sistema
¿está en un bloqueo mortal?
Creación de un grafo de espera que muestra las dependencias entre transacciones
Crear un nodo por cada transacción en ejecución, etiquetado con el identificador de la transacción, T

Si Tj espera para bloquear el elemento X, ya bloqueado por Tk, crear una arista dirigida desde Tj a Tk

Cuando Tk libera el candado sobre X, borrar la arista correspondiente
Si existe un ciclo en el grafo de espera, entonces se ha detectado un interbloqueo entre las transacciones
Técnicas de control de concurrencia
Detección de interbloqueos
(Gp:) Tj
(Gp:) Tk

(Gp:) X
(Gp:) Tj
(Gp:) Tk

43
Pero… ¿cuándo hay que verificar el estado del sistema (ejecutar el algoritmo que genera el grafo de espera)?
A intervalos uniformes de tiempo, o
A intervalos de tiempo desiguales :
Iniciar algoritmo de detección con un tamaño de intervalo inicial
Cada vez que no se detecta interbloqueo, incrementar el intervalo
Por ejemplo, al doble del anterior
Cada vez que se detecta interbloqueo, reducir el intervalo
Por ejemplo a la mitad
Existirán límites superior e inferior del tamaño del intervalo
Técnicas de control de concurrencia
Detección de interbloqueos

44
Si el sistema está en un estado de interbloqueo, el SGBD necesita abortar algunas transacciones…
¿Cuáles? ? Selección de víctimas
Es mejor abortar transacciones que lleven poco tiempo en ejecución
Es mejor abortar una transacción que haya hecho pocos cambios en la base de datos
Es mejor abortar una transacción que todavía debe hacer muchos cambios en la base de datos
Puede que el SGBD no conozca esta información
Se trata de abortar las transacciones que supongan el mínimo coste
Es necesario evitar la inanición
Técnicas de control de concurrencia
Detección de interbloqueos

45
Una transacción sufre inanición cuando es seleccionada para ser abortada (víctima) sucesivamente: nunca termina su ejecución
Es similar al bloqueo indefinido
La solución es asignar prioridades más altas a las transacciones abortadas varias veces, para no ser siempre las víctimas
Técnicas de control de concurrencia
Detección de interbloqueos: el problema de la inanición

46
El protocolo de control de concurrencia nunca selecciona a una transacción que está esperando para establecer un bloqueo, mientras otras transacciones continúan ejecutándose con normalidad
Ocurre si el esquema de espera da más prioridad a unas transacciones que a otras ? esquema de espera injusto
Dos algoritmos de prevención de bloqueo indefinido
Consiguen un esquema de espera justo
El primero que llega, es el primero en ser atendido
Las transacciones puede bloquear el elemento X en el orden en que solicitaron su bloqueo
Aumento de prioridad en la espera
Cuanto más espera T, mayor es su prioridad
Cuando T tiene la prioridad más alta de todas, obtiene el bloqueo y continúa su ejecución
Técnicas de control de concurrencia
El problema del bloqueo indefinido

47
Toda técnica de control de concurrencia supone que la base de datos está constituida por un conjunto de elementos de datos con nombre
Normalmente, un elemento de datos será uno de estos:
un valor de campo de un registro de la BD
un registro de la BD
una página (uno o varios bloques de disco)
un fichero
la BD completa
Granularidad = tamaño del elemento de información
Granularidad fina ? elementos de tamaño pequeño
Granularidad gruesa? elementos grandes
Granularidad de datos
Elementos de bases de datos y granularidad

48
En el contexto de los métodos de bloqueo, el tamaño del elemento de datos afecta al grado de concurrencia:
? tamaño(elemento) ? ? Grado de concurrencia
Y también…
? ? número de elementos en la BD
? ? carga de trabajo para la gestión de bloqueos, y
? ? espacio ocupado por la información de bloqueo
Pero… ¿Cuál es el tamaño adecuado para los elementos?
Pues depende de la naturaleza de las transacciones:
Si una T representativa accede a pocos registros
elegir granularidad de registro
Si T accede a muchos registros de un mismo fichero
elegir granularidad de página o de fichero
Granularidad de datos
Elección del tamaño adecuado del elemento de datos

49
NIVEL DE ABSTRACCIÓN LÓGICO O CONCEPTUAL:
Definición del nivel de aislamiento de cada transacción (por parte del usuario o, por omisión, el propio SGBD)
Control explícito de bloqueos (operación LOCK) por parte del usuario, si se permiten niveles de aislamiento inferiores a SERIALIZABLE
NIVEL DE ABSTRACCIÓN FÍSICO O INTERNO:
El SGBD implementa los niveles de aislamiento definidos por el usuario para las transacciones siguiendo una o varias técnicas o protocolos
Por ejemplo el SGBD Oracle usa dos:
Bloqueos
Multiversión
Estos conceptos se tratan en el anexo de este tema
Estos conceptos se han estudiado en la teoría de este tema
Aclaración …

50
Aspectos de concurrencia en SQL-92 y Oracle
SQL-92
Niveles de aislamiento de transacción
Oracle
Niveles de aislamiento de transacción
Técnica multiversión
Bloqueos (candados)

51
SQL-92
Definición de características de la transacción que se inicia
SET TRANSACTION modoacceso aislamiento
Modos de acceso
READ ONLY
Prohíbe actualizaciones
READ WRITE (por defecto)
Nivel de aislamiento
Grado de interferencia que una transacción tolera cuando se ejecuta concurrentemente con otras
READ UNCOMMITED
READ COMMITED
REPEATABLE READ
SERIALIZABLE (por defecto)

52
SQL-92
Si alguna transacción se ejecuta en algún nivel menor al SERIALIZABLE, la seriabilidad puede ser incumplida:

Si el sistema soporta niveles distintos a SERIALIZABLE, debería proporcionar facilidades de control explícito de la concurrencia (sentencias LOCK y UNLOCK…)

53
Oracle
Características de la transacción
SET TRANSACTION {READ ONLY | READ WRITE} aislamiento

Nivel de aislamiento SERIALIZABLE
Si T2 serializable intenta ejecutar una sentencia LMD que actualiza un dato que puede haber sido modificado por T1 no confirmada en el momento de comenzar T2, entonces dicha sentencia LMD falla
Una T serializable sólo ve los cambios confirmados en el instante en que se inicia, más los cambios realizados por la propia transacción mediante INSERT, UPDATE, DELETE
Nivel de aislamiento READ COMMITED (defecto)
Si T2 read-commited intenta ejecutar una sentencia LMD que necesita filas bloqueadas por T1, entonces espera hasta que se liberen los bloqueos de las filas
Cada consulta ejecutada por una transacción sólo ve los datos confirmados antes de comenzar la consulta (no la transacción)

54
Oracle
Consistencia de lectura
Garantiza que el conjunto de datos visto por una sentencia es consistente con respecto del instante en el que comenzó, y que no cambia durante la ejecución de la sentencia
Asegura que los lectores no esperan a escritores ni a otros lectores de los mismos datos
Asegura que los escritores no esperan a los lectores de los mismos datos
Asegura que los escritores sólo esperan a otros escritores si intentan modificar las mismas filas en transacciones concurrentes

55
Oracle
Implementación de consistencia de lectura
Se asemeja a que cada usuario trabaja con una copia privada de la BD (?multiversión)
Cuando ocurre una actualización, los valores originales de los datos afectados, se copian en otra zona del disco (segmentos de rollback)
Mientras la transacción T que actualiza no se confirma, cualquier usuario que consulte los datos modificados ve los valores originales
Los cambios hechos por T sólo quedan permanentes cuando T es confirmada
Las sentencias (de otras transacciones) que comienzan después de que T se confirme ya ven los cambios hechos por T
Nunca ocurren lecturas sucias

56
Oracle
Bloqueos
Gestión Automática de los bloqueos
Bloqueos exclusivos y compartidos
Permiten a otras transacciones leer los datos bloqueados, pero no modificarlos
Bloqueos de tabla o de fila (una o más)
Los bloqueos sólo se liberan la finalizar la transacción (COMMIT o ROLLBACK)
Gestión Manual
Se superpone al bloqueo automático
Sentencia LOCK TABLE (no existe UNLOCK)